package com.zhupf.graph;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author zhupf
 * @date 2023年12月18日 13:49
 * @Description
 * 994. 腐烂的橘子
 *
 * 在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
 *
 * 值 0 代表空单元格；
 * 值 1 代表新鲜橘子；
 * 值 2 代表腐烂的橘子。
 * 每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
 *
 * 返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。
 *
 */
public class OrangesRotting {

    public static void main(String[] args) {
//        int[][] grid = {{2,1,1},{1,1,0},{0,1,1}};
        int[][] grid = {{1,2}};
        orangesRotting(grid);
    }

    public static int orangesRotting(int[][] grid) {
        if(grid == null || grid.length == 0){
            return 0;
        }
        int rl = grid.length;
        int cl = grid[0].length;
        int ans = 0;
        Queue<Integer> skt = new LinkedList<>();
        for(int i = 0 ; i < rl;i++){
            for(int j = 0 ; j < cl ; j++){
                if(grid[i][j] == 2){
                    skt.add(i*cl+j);
                }
            }
        }
        int size = skt.size();
        while (!skt.isEmpty()){
            Integer node = skt.poll();
            int roll = node/cl;
            int col = node%cl;
            if(roll > 0 && grid[roll-1][col] == 1){
                grid[roll-1][col] = 2;
                skt.add((roll-1)*cl+col);
            }
            if(roll + 1 < rl && grid[roll+1][col] == 1){
                grid[roll+1][col] = 2;
                skt.add((roll+1)*cl+col);
            }
            if(col > 0 && grid[roll][col-1] == 1){
                grid[roll][col-1] = 2;
                skt.add((roll)*cl+col-1);
            }
            if(col+1 < cl && grid[roll][col+1] == 1){
                grid[roll][col+1] = 2;
                skt.add((roll)*cl+col+1);
            }
            size -- ;
            if(size == 0 && !skt.isEmpty()){
                ans++;
                size = skt.size();
            }
        }

        for(int i = 0 ; i < rl;i++){
            for(int j = 0 ; j < cl ; j++){
                if(grid[i][j] == 1){
                    ans = -1;
                }
            }
        }
        return ans;
    }
}
